πŸ‘©β€πŸ’» 9935. λ¬Έμžμ—΄ 폭발

@Seongukbaek Posted April 20, 2022 Β· Updated April 20, 2022 Β· 3 min read

문제

μƒκ·Όμ΄λŠ” λ¬Έμžμ—΄μ— 폭발 λ¬Έμžμ—΄μ„ 심어 λ†“μ•˜λ‹€. 폭발 λ¬Έμžμ—΄μ΄ ν­λ°œν•˜λ©΄ κ·Έ λ¬ΈμžλŠ” λ¬Έμžμ—΄μ—μ„œ 사라지며, 남은 λ¬Έμžμ—΄μ€ ν•©μ³μ§€κ²Œ λœλ‹€.

ν­λ°œμ€ λ‹€μŒκ³Ό 같은 κ³Όμ •μœΌλ‘œ μ§„ν–‰λœλ‹€.

  • λ¬Έμžμ—΄μ΄ 폭발 λ¬Έμžμ—΄μ„ ν¬ν•¨ν•˜κ³  μžˆλŠ” κ²½μš°μ—, λͺ¨λ“  폭발 λ¬Έμžμ—΄μ΄ ν­λ°œν•˜κ²Œ λœλ‹€. 남은 λ¬Έμžμ—΄μ„ μˆœμ„œλŒ€λ‘œ 이어 λΆ™μ—¬ μƒˆλ‘œμš΄ λ¬Έμžμ—΄μ„ λ§Œλ“ λ‹€.
  • μƒˆλ‘œ 생긴 λ¬Έμžμ—΄μ— 폭발 λ¬Έμžμ—΄μ΄ ν¬ν•¨λ˜μ–΄ μžˆμ„ μˆ˜λ„ μžˆλ‹€.
  • ν­λ°œμ€ 폭발 λ¬Έμžμ—΄μ΄ λ¬Έμžμ—΄μ— 없을 λ•ŒκΉŒμ§€ κ³„μ†λœλ‹€.

μƒκ·Όμ΄λŠ” λͺ¨λ“  폭발이 λλ‚œ 후에 μ–΄λ–€ λ¬Έμžμ—΄μ΄ λ‚¨λŠ”μ§€ ꡬ해보렀고 ν•œλ‹€. λ‚¨μ•„μžˆλŠ” λ¬Έμžκ°€ μ—†λŠ” κ²½μš°κ°€ μžˆλ‹€. μ΄λ•ŒλŠ” "FRULA"λ₯Ό 좜λ ₯ν•œλ‹€.

폭발 λ¬Έμžμ—΄μ€ 같은 문자λ₯Ό 두 개 이상 ν¬ν•¨ν•˜μ§€ μ•ŠλŠ”λ‹€.

μž…λ ₯

  • 첫째 쀄에 λ¬Έμžμ—΄μ΄ μ£Όμ–΄μ§„λ‹€. λ¬Έμžμ—΄μ˜ κΈΈμ΄λŠ” 1보닀 ν¬κ±°λ‚˜ κ°™κ³ , 1,000,000보닀 μž‘κ±°λ‚˜ κ°™λ‹€.
  • λ‘˜μ§Έ 쀄에 폭발 λ¬Έμžμ—΄μ΄ μ£Όμ–΄μ§„λ‹€. κΈΈμ΄λŠ” 1보닀 ν¬κ±°λ‚˜ κ°™κ³ , 36보닀 μž‘κ±°λ‚˜ κ°™λ‹€.
  • 두 λ¬Έμžμ—΄μ€ λͺ¨λ‘ μ•ŒνŒŒλ²³ μ†Œλ¬Έμžμ™€ λŒ€λ¬Έμž, 숫자 0, 1, ..., 9둜만 이루어져 μžˆλ‹€.

좜λ ₯

  • 첫째 쀄에 λͺ¨λ“  폭발이 λλ‚œ ν›„ 남은 λ¬Έμžμ—΄μ„ 좜λ ₯ν•œλ‹€.

πŸ“ Logic

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Graph { final int[] graph; int[] discovered; boolean[] fin; int answer = 0; int graph_size; public Graph(int size) { graph_size = size + 1; this.graph = new int[graph_size]; discovered = new int[graph_size]; fin = new boolean[graph_size]; } public void AddElement(int x, int y) { graph[x] = y; } public int solution() { for (int i=1; i < graph_size; i++) this.search(i); return graph_size - 1 - this.answer; } public void search(int node) { if (discovered[node] == 1) return; discovered[node] = 1; int next = graph[node]; if (discovered[next] == 0) search(graph[node]); else { if (!fin[next]) { // λ‹€μŒ 갈 정점이 방문은 ν–ˆμœΌλ‚˜ 아직 λλ‚˜μ§€ μ•Šμ€, 즉 사이클이 μƒμ„±λ˜μ§€ μ•Šμ€ μƒνƒœ answer++; for (int i=next; i!=node; i=graph[i]) { answer++; } } } fin[node] = true; } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); while (T > 0) { int size = sc.nextInt(); Graph g = new Graph(size); for (int i = 1; i <= size; i++) { int tmp = sc.nextInt(); g.AddElement(i, tmp); } System.out.println(g.solution()); T-=1; } sc.close(); } }

✏️ Review

  • μ²˜μŒμ—λŠ” replaceAll() ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•΄μ„œ 맀우 κ°„λ‹¨ν•œ μ½”λ“œλ‘œ κ΅¬ν˜„ν–ˆμœΌλ‚˜, 47%μ—μ„œ λ©”λͺ¨λ¦¬ μ΄ˆκ³Όκ°€ λ–΄λ‹€.

    • λ‹Ήμ—°νžˆ μ΄λ ‡κ²Œ μ‰¬μšΈ λ¦¬λŠ” μ—†λ‹€κ³  μƒκ°ν–ˆκ³ , κ²Œμ‹œνŒμ„ λ³΄λ‹ˆ replace() ν•¨μˆ˜κ°€ λ©”λͺ¨λ¦¬λ₯Ό 많이 μ‚¬μš©ν•˜λŠ” λ©”μ†Œλ“œλΌλŠ” 것을 μ•Œμ•˜λ‹€.

πŸ“• 좜처

Baekjoon : https://www.acmicpc.net/problem/9935

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€